#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

//https://leetcode.cn/problems/copy-list-with-random-pointer/

struct Node {
    int val;
    struct Node *next;
    struct Node *random;
};

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    struct Node *curr = head;
    while (curr) {
        struct Node *preNewCurr = (struct Node *) malloc(sizeof(struct Node));
        preNewCurr->val = curr->val;
        preNewCurr->next = curr->next;
        curr->next = preNewCurr;
        curr = preNewCurr->next;
    }
    curr = head;
    while (curr) {
        if (curr->random == NULL) {
            curr->next->random = NULL;
        } else {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }
    struct Node *preHead = (struct Node *) malloc(sizeof(struct Node));
    struct Node *preNewHead = (struct Node *) malloc(sizeof(struct Node));
    struct Node *preCurr = preHead;
    struct Node *preNewCurr = preNewHead;
    curr = head;
    while (curr) {
        preCurr->next = curr;
        preNewCurr->next = curr->next;
        curr = curr->next->next;
        preCurr = preCurr->next;
        preNewCurr = preNewCurr->next;
    }
    return preNewHead->next;
}


int main() {

    return 0;
}